﻿//Write a program that sorts an array of strings using the quick sort algorithm (find it in Wikipedia).

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _14QuickSortAlgo
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Array size:");
            string strArraySize = Console.ReadLine();
            int arraySize = int.Parse(strArraySize);
            string[] array = new string[arraySize];
            for (int i = 0; i <= array.Length - 1; i++)
            {
                Console.Write("array[{0}]:", i);
                array[i] = Console.ReadLine();
            }
            Console.WriteLine("The array looks like this:");
            foreach (var item in array)
            {
                Console.Write(item + " ");
            }

            Quicksort(array, 0, array.Length - 1);

            Console.WriteLine();
            Console.WriteLine("After quicksort the array looks like this:");
            foreach (var item in array)
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();
        }

        public static void Quicksort(IComparable[] elements, int left, int right)
        {
            int i = left, j = right;
            IComparable pivot = elements[(left + right) / 2];

            while (i <= j)
            {
                while (elements[i].CompareTo(pivot) < 0)
                {
                    i++;
                }

                while (elements[j].CompareTo(pivot) > 0)
                {
                    j--;
                }

                if (i <= j)
                {
                    // Swap
                    IComparable tmp = elements[i];
                    elements[i] = elements[j];
                    elements[j] = tmp;

                    i++;
                    j--;
                }
            }

            // Recursive calls
            if (left < j)
            {
                Quicksort(elements, left, j);
            }

            if (i < right)
            {
                Quicksort(elements, i, right);
            }
        }
    }
}
